package org.example.l0;

import java.util.Comparator;
import java.util.PriorityQueue;

class MedianFinder {

    PriorityQueue<Integer> lt = new PriorityQueue<>(Comparator.reverseOrder());
    PriorityQueue<Integer> gt = new PriorityQueue<>();

    public MedianFinder() {
    }

    public void addNum(int num) {
        if (lt.isEmpty() || num <= lt.peek()) {
            lt.offer(num);
            if (gt.size() + 1 < lt.size()) {
                gt.offer(lt.poll());
            }
        } else {
            gt.offer(num);
            if (gt.size() > lt.size()) {
                lt.offer(gt.poll());
            }
        }
    }

    public double findMedian() {
        if (lt.size() == gt.size()) {
            return (lt.peek() + gt.peek()) / 2.0;
        }

        return lt.peek();
    }
}